package algorithm.graph;

import lombok.Data;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/5/19 18:40
 */
public abstract class Graph<V, E> {
    public WeightManager<E> weightManager;

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    public abstract int edgesSize();

    public abstract int verticesSize();

    public abstract void addVertex(V v);

    public abstract void addEdge(V from, V to);

    public abstract void addEdge(V from, V to, E weight);

    public abstract void removeVertex(V v);

    public abstract void removeEdge(V from, V to);

    public abstract void bfs(V begin, VertexVisitor<V> visitor);

    // 递归实现
    public abstract void dfs(V begin, VertexVisitor<V> visitor);

    // 非递归实现
    public abstract void dfs1(V begin, VertexVisitor<V> visitor);

    // 拓扑排序
    public abstract List<V> topologicalSort();

    // 最小生成树
    public abstract Set<EdgeInfo<V, E>> mst();

    /**
     * 单源最短路径
     * 给出的信息不仅仅是权值，还包括经过了哪些顶点，哪些边，所以用PathInfo来封装
     * @param begin
     * @return
     */
    public abstract Map<V, PathInfo<V, E>> shortestPath(V begin);

    // 多源最短路径
    public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPath();

    public abstract void print();

    public interface VertexVisitor<V> {
        boolean visit(V v);
    }

    public interface WeightManager<E> {
        int compare(E w1, E w2);
        E add(E w1, E w2);
        E zero();
    }

    @Data
    public static class EdgeInfo<V, E> {
        private V from;
        private V to;
        private E weight;

        public EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    @Data
    public static class PathInfo<V, E> {
        private E weight;
        private List<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();
        public PathInfo() {}
        public PathInfo(E weight) {
            this.weight = weight;
        }

        // 用于打印
        @Override
        public String toString() {
            return "PathInfo{" +
                    "weight=" + weight +
                    ", edgeInfos=" + edgeInfos +
                    '}';
        }
    }
}
